package DivideAndConquer;

import java.util.Random;

/**
 * 合并排序
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/15 20:52
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] a = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            a[i] = random.nextInt(101);
        }
        for (int num : a)  System.out.print(num +  " ");
        System.out.println();

        mergeSort(a, 0, 9);

        for (int num : a)  System.out.print(num + " ");

    }

    static final int len = 1024;

    static void mergeSort(int[] a, int low, int high) {
        int middle;
        if (low < high) {
            middle = (low + high) / 2; // 取中点
            mergeSort(a, low, middle); // 左子列
            mergeSort(a, middle + 1, high); //右子列
            merge(a, low, middle, high); //合并
        }
    }

    static void merge(int[] a, int low, int middle, int high) {
        int i, j, k;
        int[] b = new int[len];
        i = low;
        j = middle + 1;
        k = low;
        while (i <= middle && j <= high) {
            if (a[i] <= a[j]) {
                b[k++] = a[i++];
            } else {
                b[k++] = a[j++];
            }
        }
        while (i <= middle) b[k++] = a[i++];//左子列未遍历完
        while (j <= high) b[k++] = a[j++];//右子列未遍历完
        for (i = low; i <= high; i++) a[i] = b[i];//将排序完成的子数列放回数组
    }
}
